import java.util.ArrayList;

/**
 * @version Create on 2012-10-29
 * @author Yinzi Chen
 */

public class Combinations {
	ArrayList<ArrayList<Integer>> res;
	ArrayList<Integer> list;
	int n, k;

	void search(int val, int cnt) {
		if (cnt == k) {
			res.add((ArrayList<Integer>) list.clone());
			return;
		}
		if (val == n)
			return;
		search(val + 1, cnt);
		list.add(val + 1);
		search(val + 1, cnt + 1);
		list.remove(list.size() - 1);
	}

	public ArrayList<ArrayList<Integer>> combine(int n, int k) {
		this.n = n;
		this.k = k;
		res = new ArrayList<ArrayList<Integer>>();
		list = new ArrayList<Integer>();
		search(0, 0);
		return res;
	}

	public static void main(String[] args) {

	}

}
